package _08_DFS;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 * @Author: haogege
 * @Date: 2021/8/31
 */
public class _17_电话号码的字母组合 {

    private char[][] lettersArray = {
            {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
            {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}
    };

    char[] chars;

    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.length() == 0) return list;
        chars = digits.toCharArray();
        char[] result  = new char[chars.length];
        dfs(0, result, list);
        return list;
    }

    private void dfs(int i, char[] result, List<String> list) {
        if (i == result.length) {
            list.add(new String(result));
        }

        // 遍历每一层出现的所有可能
        int index = chars[i] - '2';
        char[] let = lettersArray[index];
        for (char c : let) {
            result[i] = c;
            dfs(i + 1, result, list);
        }
    }

}
